The present invention relates to a viterbi decoder and, more particularly, to a viterbi decoder having a reduced decoding time with respect to encoded convolutional codes.
A viterbi decoder uses the well known viterbi algorithm when a received convolutional codeword is to be decoded. The viterbi algorithm depends on maximum likelihood decoding. The Viterbi algorithm compares aplurality of known code sequences with received code sequences, selects the path having the shortest code distance as a maximum likelihood path, and obtains decoded data corresponding to the selected path. The viterbi algorithm exhibits excellent error correction capability. Thus, it is widely used in satellite, ground network, and mobile communications.
The principles of viterbi decoding are described, for example, in xe2x80x9cCDMA Principles of Spread Spectrum Communicationxe2x80x9d by A. J. VITERBI, ADDISON-WESLEY PUBLISHING COMPANY, pp.132-138, April, 1995. An example of the viterbi decoder is disclosed in U.S. Pat. No. 5,295,142 issued on Mar. 15, 1994.
In a code division multiple access (CDMA) mobile station, the operational timing of the viterbi decoder relates to three channel types (i.e., sync, paging, and traffic channels) of the four forward CDMA channels. The forward CDMA channel corresponds to communications from a base station (cell) to a mobile station.
In mobile communications, technical requirements are specified by air interface standards such as IS-95A and ANSI J-STD-008. They ensure that mobile stations can obtain service in any cellular system manufactured according to these standards. The IS-95A specification for wideband spread spectrum cellular mobile telephones, supports a 9,600 bps rate family in the three data channeling types (sync, paging, and traffic channels). This is referred to as Rate Set 1. In all cases, the forward error correction (FEC) code rate is xc2xd. The J-STD-008 specification for CDMA personal communications services systems (PCS) supplies, in addition to the above Rate Set 1, a second traffic channel rate family with a maximum rate of 14,400 bps. This is referred to as Rate Set 2. Rate Set 2 uses an FEC code rate of xc2xe, created by puncturing (deleting) the code used in Rate Set 1.
Rate Set 2 yields the same code symbol rate as Rate Set 1 with {fraction (3/2)} times the data rate. Traffic channels carry variable traffic frames of either 1, xc2xd, xc2xc, or xe2x85x9 times the full rate. The rate variation is accomplished by 1, 2, 4, or 8-way repetition of code symbols.
A system employing the CDMA communication method uses a viterbi decoder that includes a single add-compare-select (ACS) unit. The decoder usually uses a convolutional codeword with a constrained length K of 9 and, thus, the number of states is 29xe2x88x921, namely, 256. Therefore, the single ACS unit performs addition, comparison, and selection on 256 states for one symbol.
FIG. 1 is a schematic block diagram of a conventional viterbi decoder. The viterbi decoder includes a controller 10, an input buffer 20, a symbol metric table (SMT) unit 30, a branch metric calculate unit 40, an ACS unit 50, a traceback unit 60, and an output buffer 70. The controller 10 generates a variety of control signals (hereinafter collectively represented by the reference symbol xe2x80x9cCTLxe2x80x9d) after a frame synchronous signal F_Sync is activated. The viterbi decoder decodes an input symbol IN_DATA and outputs decoded data DECODED DATA under the control of the control signals CTL from the controller 10.
FIG. 2 is a block diagram illustrating the ACS unit 50 of FIG. 1. The ACS unit 50 includes an ACS controller 51, an ACS calculating unit 52, a first register 53, delays 54, first and second memories 55 and 56, a multiplexer 57, and a second register 58.
The first and the second memories 55 and 56 are random access memories (RAMs) for storing state metrics. Each state metric includes 5 bits and 1 quality bit. The first and the second memories 55 and 56 can store 128*12 bits, respectively.
The first register 53 is used for storing a current state metric SM(i+1) from the ACS calculating unit 52. The second register 58 is used for storing a previous state metric SM(i) from the multiplexer 57.
The ACS controller 51 generates a write enable signal WEN, an access control signal CSN, and a selection signal S in response to the control signals CTL from the controller 10. The write enable signal WEN and the access control signal CSN are supplied to the first and the second memories 55 and 56 to write and access the state metrics, respectively. The multiplexer 57 outputs the previous state metric SM(i) stored in the first memory 55 or the second memory 56 to the register 58 in response to the selection signal S. The ACS calculating unit 52 has an adder for adding the state metric SM(i) and branch metric BM(i) to obtain new state metric SM(i+1), a comparator for comparing the new state metric, and a selector for selecting one of the new state metrics SM(i+1) to be output in response to the output of the comparator.
When the input data IN_DATA is input, the branch metric unit 40 calculates the Euclidean distance or the Hamming distance between the received data and a codeword to be transmitted, and supplies the result of the calculation (i.e., branch metric) to the ACS unit 50. In the ACS calculating unit 52, the branch metric BM(i) is added to previous state metric SM(i) in the adder according to a trellis diagram, currently received state metrics are compared in the comparator, and small state metrics are selected in the selector. The selected state metrics are stored in the memory 55 or 56 as a current state metric SM(i+1). Meanwhile, selected path information P(i+1) of the current state is stored in a path memory (not shown) after passing through the traceback unit 60. The traceback unit 60 traces the path information to look for a state having the largest maximum likelihood, finds the most approximate path to that of data sent from a transmitting encoder (not shown), and outputs decoded data DECODED DATA through the output buffer 70.
FIG. 3 is a trellis diagram illustrating the allowable transitions from state to state for the ACS unit 50 of FIG. 2. The state metric of an xe2x80x98axe2x80x99 state in the ith stage is expressed as SMai, and the branch metric from the xe2x80x98axe2x80x99 state in the ith stage to a xe2x80x98bxe2x80x99 state in the (i+1) stage is expressed as BMa,bi. In that case, the state metric of the (i+1)th stage is defined as follows:
SMci+1=min(SMai+BMa,ci,SMbi+BMb,ci)xe2x80x83xe2x80x83(1)
For example, as shown in FIG. 3, the state metric SM128i+1 is obtained from the state metrics SM0i and SM1i and the branch metrics BM0,128i and BM1,128i. The process of obtaining the current state metric is called ACS calculating, since adding, comparing and selecting are required to determine the current state metric, as shown in equation (1).
Referring to FIGS. 2 and 3, in the ith stage, the first memory 55 stores the state metrics of xe2x80x98axe2x80x99 state in the ith stage SMai, and the second memory 56 stores the state metrics of xe2x80x98bxe2x80x99 state in the (i+1)th stage SMbi+1.
In the ACS unit 50, the first and the second memories 55 and 56 are initialized at the first stage. After initialization, the state metric SM(i) is read from the first memory 55 to calculate the current state metric SM(i+1). The calculated current state metric SM(i+1) is stored in the second memory 56. Reading and writing periods of the first and the second memories 55 and 56 are repeated every other stage. Each of the memories 55 and 56 spends 2 clock cycles for the reading/writing operation. Thus, (256+xcex1) clock cycles are needed for 1 stage processing, wherein xcex1 is a delay time of the ACS calculating unit 52.
For example, in the ith stage, the ACS unit 50 calculates SM0i+1 and SM128i+1 by reading the state metrics SM0i and SM1i, and calculates SM1i+1 and SM129i+1 by reading the state metrics SM2i and SM3i. The calculated state metrics SM0i+1 and SM1i+1 are stored in the second memory 56, when the state metrics SM4i and SM5i are read out from the first memory 55. The state metrics SM128i+1 and SM129i+1 are stored in the second memory 56, when the state metrics SM6i and SM7i are read out from the first memory 55. The ACS calculating process of the ith stage is not terminated until it is applied to all states of the ith stage. Thus, the ACS calculating time depends upon the frame size. Since the frame size of Rate Set 2 is approximately 1.5 times as large as Rate Set 1, the ACS calculating time of Rate Set 2 is longer than that of Rate Set 1.
In ACS calculating, despite being accumulated in the state metrics, normalization and saturation processes are executed every stage to prevent overflow of the state memories 55 and 56, since the state metrics are only 5 bits. Thus, in the ACS unit 50 having the single ACS calculating unit 52, ACS calculating of the three stages requires three steps to process the puncturing pattern xe2x80x98110101xe2x80x99. In that case, the current state metric SM(i+1), considering the normalization and saturation processes, is expressed as follows:
SMci+1=min(SMaixe2x88x92mS+BMa,ci,SMbixe2x88x92mS+BMb,ci,31)xe2x80x83xe2x80x83(2)
mS=mink=0,255(SMki)
FIG. 4 is a timing diagram illustrating the operation of the conventional viterbi decoder in the forward traffic channel. In the forward traffic channel, the period for one frame is 20 ms. Thus, the frame synchronous signal F_Sync is generated every 20 ms. When the frame synchronous signal F_Sync is activated, the viterbi decoder performs the decoding process after inputting the frame data therein. The frame data input time Tin for inputting the frame data is much less than 1 ms. After the frame data decoding process, the decoded data is read by a central processing unit (CPU) (not shown) before the start of the next frame decoding process. The frame data decoding time Tdec is approximately 11.3 ms in Rate Set 1, and approximately 16 ms in Rate Set 2. A time for reading the decoded frame data, i.e., a frame data reading time Tread is measured about 8.7 ms in the Rate Set 1, and 4 ms in the Rate Set 2, respectively. The frame data reading time Tread is defined as follows:
Tread=20 msxe2x88x92Tdecxe2x80x83xe2x80x83(3)
As shown in equation (3), the frame data reading time Tread depends upon the frame data decoding time Tdec. The frame data reading time Tread decreases as the frame data decoding time Tdec increases. Thus, it is possible that the CPU cannot read the decoded frame data correctly if the frame data reading time Tread is shortened. As described above, the frame data reading time Tread in the Rate Set 1 is approximately 8.7 ms, so that the frame data reading time Tread is sufficient to correctly read the frame data. The frame data reading time Tread in Rate Set 2 is approximately 4 ms. In that case, it is possible that the frame data is not able to be read correctly during the frame data reading time Tread. Thus, there is a need to reduce the decoding time of the viterbi decoder in Rate Set 2.
The present invention is directed to a viterbi decoder having a reduced decoding time of encoded convolutional codes.
According to an aspect of the present invention, there is provided a viterbi decoder for decoding convolutional data. The convolutional data includes punctured data and non punctured data. The decoder includes a branch metric unit for calculating branch metrics of the received convolutional data. An add-compare-select unit selects current and next path selection information and calculates a current state metric and a next state metric of the punctured data, from the branch metrics and a previous state metric. A traceback unit traces the current and the next path selection information selected in the add-compare-select unit to find a maximum likelihood path from which the convolutional data was received, and outputs decoded data. A controller generates a plurality of decoding control signals to the branch metric unit, the add-compare-select unit, and the traceback unit.
According to another aspect of the present invention, the add-compare-select unit includes an add-compare-select control device for generating a write enable signal, an access control signal, and a selection signal, in response to a plurality of control signals from the controller including a puncturing stage control signal. A first and a second storing device store the current state metric or the next state metric in response to the write enable signal, and read out the previous state metric stored therein in response to the access control signal. A first selection device outputs the current state metric or the next state metric to the storing device in response to the puncturing stage control signal. A register stores the previous state metric outputted from the first selection device. A first add-compare-select calculating device adds, compares, and selects the branch metrics and the previous state metric from the register, and generates the current state metric and the current path selection information. A second add-compare-select calculating device adds, compares, and selects the next branch metric and the current state metric from the first add-compare-select calculating device, and generates the next state metric and the next path selection information. A second selection device outputs the previous state metric in response to the selection signal.